package com.cg.leetcode;

import org.junit.Test;

/**
 * 108. 将有序数组转换为二叉搜索树
 *
 * @program: LeetCode->LeetCode_108
 * @description: 108. 将有序数组转换为二叉搜索树
 * @author: cg
 * @create: 2021-08-21 00:29
 **/
public class LeetCode_108 {

    @Test
    public void test108() {
        System.out.println(sortedArrayToBST(new int[]{-10,-3,0,5,9}));
    }

    /**
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     *
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     *
     * 示例 1：
     *       0
     *      / \
     *    -3  9
     *   /   /
     * -10  5
     * 输入：nums = [-10,-3,0,5,9]
     * 输出：[0,-3,9,-10,null,5]
     * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
     *       0
     *      / \
     *    -10  5
     *      \   \
     *      -3   9
     *
     * 示例 2：
     *   3    1
     *  /      \
     * 1        3
     * 输入：nums = [1,3]
     * 输出：[3,1]
     * 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        if (left > right) {
            return null;
        }
        return new TreeNode(nums[mid], helper(nums, left, mid - 1), helper(nums, mid + 1, right));
    }

}
